<!DOCTYPE html>
<html>

<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
    <link rel="apple-touch-icon" sizes="60x60" href="https://fziks.gitee.io/icons/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="https://fziks.gitee.io/icons/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="https://fziks.gitee.io/icons/favicon-16x16.png">
<link rel="manifest" href="https://fziks.gitee.io/icons/site.webmanifest">
<link rel="mask-icon" href="https://fziks.gitee.io/icons/safari-pinned-tab.svg" color="#5bbad5">
<link rel="shortcut icon" href="https://fziks.gitee.io/icons/favicon.ico">
<meta name="msapplication-TileColor" content="#ffffff">
<meta name="msapplication-config" content="/icons/browserconfig.xml">
<meta name="theme-color" content="#ffffff">
    
<link rel="stylesheet" href="//at.alicdn.com/t/font_1559566_wk214kwa2dn.css">


    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/katex.min.css" integrity="sha384-zB1R0rpPzHqg7Kpt0Aljp8JPLqbXI3bhnPWROx27a9N0Ll6ZP/+DiW/UqRcLbRjq" crossorigin="anonymous">



    
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/normalize/8.0.1/normalize.css" integrity="sha256-WAgYcAck1C1/zEl5sBl5cfyhxtLgKGdpI3oKyJffVRI=" crossorigin="anonymous" />
    
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.7.2/animate.css" integrity="sha256-a2tobsqlbgLsWs7ZVUGgP5IvWZsx8bTNQpzsqCSm5mk=" crossorigin="anonymous" />
    
   <link href="https://stackpath.bootstrapcdn.com/bootswatch/4.4.1/materia/bootstrap.min.css" rel="stylesheet" integrity="sha384-1tymk6x9Y5K+OF0tlmG2fDRcn67QGzBkiM3IgtJ3VrtGrIi5ryhHjKjeeS60f1FA" crossorigin="anonymous">
    
    
    <link rel="stylesheet" href="https://fziks.gitee.io/sass/main_cdn.min.270b43bb8631af4497ed45b90db42c517e86c9511418de9152f134d02ed32b87.min.2192baea245cf318085511589e62bfbdb3fbe4fb0eef718f1be9af91c10542ce.css" integity="sha256-IZK66iRc8xgIVRFYnmK/vbP75PsO73GPG&#43;mvkcEFQs4=">

    <link rel="stylesheet" href="https://fziks.gitee.io/css/wiki.css" />
    <link rel="stylesheet" href="https://fziks.gitee.io/css/slides.css" />
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.css">
    <title>OSC Chapt.5</title>
    <style>
        div.remark-footer {
            bottom: 12px;
            opacity: .5;
            position: absolute;
            left: 20px;
        }
        .remark-slide > .remark-title,
        .remark-slide > .remark-center {
            text-align: center;
        }
        .remark-slide > .remark-title,
        .remark-slide > .remark-middle {
            vertical-align: middle;
        }
    </style>
</head>

<body>
    <p id="loading">Loading OSC Chapt.5</p>
    <textarea id="source" class="d-none">

layout:true
&lt;div class="remark-footer">Ap Chen&lt;/div>
---

class: remark-title
# OSC Chapt.5
&lt;div style="display: flex; justify-content: center; text-align: center;" id="qrcode">&lt;/div>
&lt;div class="my-3">https://fziks.gitee.io/slides/osc-chapt.5/&lt;/div>
2020-06-26 08:00 CST
---


- 进程调度和线程调度通常是可替换的
- 多核系统比单核系统在进程等待时运行更有效率

--
- Incorporating I/O:任务执行I/O操作时会被阻塞，直到I/O操作完成。如果进行硬件读写，就可能会导致几毫秒的等待。因此，调度算法必须在I/O操作出现时合理的切换到别的任务。
  - 一种通常的解决方法是把进程的每一个部分都当作一个独立的任务。如果进程发起I/O请求，那么这个子任务就结束，OS可以切换到下一个任务。这样做出现了重叠(overlap)，CPU可以在等待I/O的时间内执行另一个任务，更好地利用资源。

---

## 调度算法

- 关注的进程性能：CPU执行转数、 I/O等待
- 算法实现关键：An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a few long CPU bursts.
- 在四种情况下发生：1running to waiting 、2running to ready 、3waiting to ready 、 4terminates
- 1、4不剥夺，2、3是剥夺

---

## 单核调度算法

---

### First Come, First Served (FCFS)

实现简单，不适合交互系统

但如果每个任务所需时间不同，FIFO的效果就很差。大部分小的任务排在了一个大任务的后面，称为**护卫效应**(convoy effect)。

---


### Shortest Job First (SJF)

严格意义上为Shortest-next-CPU-burst algorithm，选择下一个更短的CPU burst进程，如果两进程相同则FCFS。

因为我们假设所有任务同时到来，所以在这个条件下可以保证SJF是最优调度算法（贪心）。


- 剥夺（一般效果更好）和非剥夺式
- 优化了平均等待时间，但未实现等级调度

预测公式 $\tau_{n&#43;1} = \alpha t_n &#43; (1-\alpha)\tau_n$

$\alpha$是**最近**和**历史**的权重比，取值小于1。If 0 then 与最近无关联 ；If 1/2 then最近和历史权重相等

 $t_n$是最近信息， $\tau_n$是历史记录。

---

### **Round Robin**(RR)

每次花一段时间(time slice/scheduling quantum)执行一个任务，然后切换到队列的下一个任务。因此，RR也被叫做**time-slicing**。

对于RR算法来说，决定一次运行的时间是非常重要的。运行时间越短，在响应时间标准下RR效果越好，但切换上下文的开销会拖累总体的性能。因此，时间切片的长度是一个trade-off，时间长可以**均摊**(amortize)切换上下文的开销。

--
&gt; ##### TIP: Amortization Can Reduce Costs
&gt;
&gt; The general technique of **amortization** is commonly used in systems when there is a ﬁxed cost to some operation. By incurring that cost less often (i.e., by performing the operation fewer times), the total cost to the system is reduced. For example, if the time slice is set to 10 ms, and the context-switch cost is 1 ms, roughly 10% of time is spent context switching and is thus wasted. If we want to *amortize* this cost, we can increase the time slice, e.g., to 100 ms. In this case, less than 1% of time is spent context switching, and thus the cost of time-slicing has been amortized.

但是RR在完成时间上并不是一个高效的策略，甚至比FIFO还差。

---

笼统地说，任何通过划分CPU执行时间来保持**公平**的调度算法都在完成时间上效果不咋地。实际上，这是一个内在的trade-off：如果你要不公平，你可以让跑得快的任务早点完成，但是响应时间就很长；否则，你要减少响应时间，完成时间就会很长。此类**trade-off**在系统中非常常见，鱼和熊掌不可兼得。

至此，共有两类调度算法：第一类(SJF, STCF)优化完成时间，但响应时间高；第二类(RR)优化响应时间，但完成时间长。

STCF: Short Time to Complete First

---

### MLFQ

有一些不同的**队列**(queue)，每个都有不同的**优先级**(priority level)。在任意时刻，一个即将运行的任务只会在一个队列中。MLFQ利用优先级来决定运行谁：选择一个具有更高优先级（位于更高队列中）的任务继续执行。

同一队列且各任务优先级相同则为RR算法

- 规则1：如果A的优先级大于B的优先级，运行A；
- 规则2：如果A、B优先级相同，用RR调度它们。
- 规则3：当一个程序进入系统，默认优先级是最高的。
- 规则4a：如果程序使用了整段运行时间，降低优先级；
- 规则4b：如果程序在时间结束前主动放弃CPU，保持优先级不变。
- 规则5：经过一段时间S*S*后，把系统中的所有任务移动到最高优先级队列中。

如何阻止用户恶意利用调度规则？解决方案是让调度算法对CPU使用时间做出更好的统计。

--

- 改进规则4：一旦程序用完了对应优先级允许的运行时间（无论放弃了多少次CPU），都把它移动到次优先级。

---

### Ticket Mechanisms
- 全局的彩票货币
- 彩票交易 （C/S）
- 通货膨胀 （互相信任的程序之间使用）

--

- 改进为公平方法：步长调度（利用步长和pass决定下一次运行谁）
  步长和彩票数成反比；pass选最低的，用时pass增加

---

### CFS

- 红黑树实现

        
---

class: remark-title
# Thanks

    </textarea><script defer src="https://remarkjs.com/downloads/remark-latest.min.js"></script>
    
    <script type="text/javascript" src="https://fziks.gitee.io/qrcode.min.08d80845e706a3b9e985b799d3849cd7791ad3ba5aa9d793bb4591d4833890d7299810144874905f416c94d8530da74be0ee520066a91ade05a1da8bf0ccb498.js" integrity="sha512-CNgIRecGo7nphbeZ04Sc13ka07paqdeTu0WR1IM4kNcpmBAUSHSQX0FslNhTDadL4O5SAGapGt4FodqL8My0mA=="></script><script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/katex.min.js" integrity="sha384-y23I5Q6l+B6vatafAwxRu/0oK/79VlbSz7Q9aiSZUvyWYIYsd+qj+o24G5ZU2zJz" crossorigin="anonymous"></script>
    <script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/contrib/auto-render.min.js" integrity="sha384-kWPLUVMOks5AQFrykwIup5lo0m3iMkkHrD0uJ4H5cjeGihAutqP0yW0J6dpFiVkI" crossorigin="anonymous"
onload="renderMathInElement(document.body);"></script>

    <script>
        document.addEventListener("DOMContentLoaded", function () {
            
            const slides = remark.create({});
            const qrcode = new QRCode(document.getElementById("qrcode"), {
                text: "https:\/\/fziks.gitee.io\/slides\/osc-chapt.5\/",
                width: 128,
                height: 128,
            });
            renderMathInElement(document.body, {
                delimiters: [
                    {
                        left: "$$",
                        right: "$$",
                        display: true
                    },
                    {
                        left: "$",
                        right: "$",
                        display: false
                    },
                    {
                        left: "\\[",
                        right: "\\]",
                        display: true
                    },
                    {
                        left: "\\(",
                        right: "\\)",
                        display: false
                    },
                ]
            });
            document.getElementById("loading").classList.add("d-none");
        });
    </script>
</body>

</html>
